package main

import (
	"container/list"
	"fmt"
)

// 用map和链表实现LRU缓存
type LRUCache struct {
	cache map[int]int
	lst   list.List
	Cap   int
}

func NewLRUCache(cap int) *LRUCache {
	lru := new(LRUCache)
	lru.cache = make(map[int]int, cap)
	lru.lst = list.List{}
	lru.Cap = cap
	return lru
}

func (lru *LRUCache) Add(k int, v int) {
	if lru.lst.Len() >= lru.Cap {
		//先删除队尾元素
		back := lru.lst.Back()
		delete(lru.cache, back.Value.(int))
		lru.lst.Remove(back)
		//再插入新的元素
		lru.cache[k] = v
		lru.lst.PushFront(k)
	} else {
		lru.cache[k] = v
		lru.lst.PushFront(k)
	}
}

func (lru *LRUCache) Find(k int) *list.Element {
	if lru.lst.Len() == 0 {
		return nil
	} else {
		head := lru.lst.Front()
		for {
			if head == nil {
				break
			} else {
				if head.Value.(int) == k {
					return head
				} else {
					head = head.Next()
				}
			}
		}

		return nil
	}
}

func (lru *LRUCache) Get(k int) (int, bool) {
	val, isTure := lru.cache[k]
	if !isTure {
		return 0, false
	}
	ele := lru.Find(k)
	if ele != nil {
		lru.lst.MoveToFront(ele)
	}
	return val, isTure
}

func main() {
	cache := NewLRUCache(10)

	for i := 0; i < 10; i++ {
		cache.Add(i, i)
	}

	fmt.Println(cache.cache)

	for i := 0; i < 10; i += 2 {
		cache.Get(i)
	}

	fmt.Println(cache.cache)

	for i := 10; i < 15; i++ {
		cache.Add(i, i)
	}

	fmt.Println(cache.cache)
}
